package jianzhi_offer;

//求数组逆序对 用二叉搜索树
public class _34_数组中的逆序对 {
    class Node{//构造二叉搜索树
        int val;
        int now;
        Node left;
        Node right;
        public Node(int val){
            this.val = val;
            this.now = 1;
        }
    }

    public static void main(String[] args) {
        _34_数组中的逆序对 test = new _34_数组中的逆序对();
        System.out.println(test.InversePairs1(new int[]{1,2,3,4,5,6,7,0}));
    }

    //暴力解 双重循环超时
    public int InversePairs(int [] array) {
        int MOD = 1000000007;
        int ans = 0;
        if(array == null || array.length <= 1) return 0;
        for(int i=1;i<array.length;++i){
            int now = 0;
            for(int j=i-1;j>=0;--j){
                if(array[j] > array[i]){
                    ++now;
                }
            }
            ans = (ans+now)%MOD;
        }
        return ans;
    }

    //用二叉搜索树
    public int InversePairs1(int [] array) {
        if(array == null || array.length <= 1) return 0;
        int MOD = 1000000007;
        int ans = 0;
        Node root = new Node(array[0]);
        for(int i=1;i<array.length;++i){
            int now = insert(root,array[i]);//logNow
            ans = (ans+now)%MOD;
        }
        return ans;
    }

    //插入某个节点到二叉树中 统计当前产生多少逆序对
    public int insert(Node root,int val){
        int ans = 0;
        while(root != null){
            if(val > root.val){//要插到右子树中
                root.now++;
                if(root.right == null){
                    root.right = new Node(val);
                    return ans;
                }
                root = root.right;
            }else{
                ans += root.now;
                if(root.left == null){
                    root.left = new Node(val);
                    return ans;
                }
                root = root.left;
            }
        }
        return ans;//达不到的
    }
}
